package sort;

import java.util.ArrayList;

public class BucketSort {
    public static void bucketSort(int [] nums , int bucketCount){
        //先找出min和max
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int num : nums) {
            min = Math.min(min,num);
            max = Math.max(max,num);
        }

        //计算偏移量，将nums投影到[0....)中
        int offset = -min;
        int bucketSize = (max-min) / bucketCount + 1;

        //创建桶
        ArrayList<Integer> [] bucket = new ArrayList[bucketCount];
        //初始化桶
        for (int i = 0 ; i < bucketCount ; i++) {
            bucket[i] = new ArrayList<>();
        }

        //将元素投影到桶中
        for (int num : nums) {
            int index = (num+offset)/bucketSize;
            bucket[index].add(num);
        }

        //在每个桶中进行排序
        for (int i = 0; i < bucketCount; i++) {
            insertSort(bucket[i]);
        }

        //集成
        int index = 0;
        for (int i = 0; i < bucketCount; i++) {
            for (Integer num : bucket[i]) {
                nums[index] = num;
                index++;
            }
        }
    }

    private  static void insertSort(ArrayList<Integer> nums) {
        int sortIndex = 0;
        while(sortIndex< nums.size()){

            for (int i = sortIndex; i > 0 ; i--) {
                if (nums.get(i) < nums.get(i-1)){
                    int temp = nums.get(i);
                    nums.set(i, nums.get(i-1));
                    nums.set(i-1 , temp);
                }else
                    break;
            }

            sortIndex++;
        }
    }

    public static void printArray(int [] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int [] array = {9,5,8,6,6,4,3,8,5,7};
        bucketSort(array,10);
        printArray(array);
    }
}
